Bibliotecas Utilizadas#
Time: medição de tempo de execução para graficos comparativos Plotly: plotagem das figuras animadas e graficos
import time
import plotly.graph_objects as go
import os
Classes Base#
A classe Vertex representa cada um dos vértices passados pela entrada e armazena as coordenadas do vértice, o índice dele, a cor dele e os índices de seus vizinhos.
class Vertex:
def __init__(self,x_coord, y_coord,next_index, prev_index, index):
self.x = x_coord
self.y = y_coord
self.next = next_index
self.prev = prev_index
self.index = index
self.color = None
A classe Polygon representa o poligono passado na entrada, ela armazena a lista de vértices que formam o poligono, a lista de coordenadas x e a lista de coordenadas y. Como funções, possui a Init responsável pela leitura do arquivo de entrada e criação dos vertices. E a função plot, responsável por exibir o poligono e seu processo de triangulação.
class Polygon:
def __init__(self, filename):
self.x_coords = []
self.y_coords = []
self.vertex_list = []
with open(filename, 'r') as file:
for line in file:
parts = line.strip().split()
num_vertices = int(parts[0])
#print(num_vertices)
for i in range(num_vertices):
x_str, y_str = parts[2 * i + 1], parts[2 * i + 2]
num, dem = map(int, x_str.split('/'))
x_coord = num / dem
self.x_coords.append(x_coord)
num, dem = map(int, y_str.split('/'))
y_coord = num / dem
self.y_coords.append(y_coord)
self.vertex_list.append(Vertex(x_coord, y_coord, (i+1)%num_vertices, (i-1)%num_vertices , i))
def plot(self, triangles=None):
fig = go.Figure()
fig.add_trace(go.Scatter(x=self.x_coords + [self.x_coords[0]], y=self.y_coords + [self.y_coords[0]], fill='toself', fillcolor='rgba(0, 0, 139, 0.2)',
mode='lines+markers', name='Triangle'))
fig.update_layout(
xaxis=dict(title='X'),
yaxis=dict(title='Y'),
showlegend=True,
hovermode='closest',
template='plotly_white',
updatemenus=[{'type': 'buttons',
'buttons': [{'label': 'Play',
'method': 'animate',
'args': [None, {'frame': {'duration': 500, 'redraw': True}, 'fromcurrent': True, 'transition': {'duration': 300, 'easing': 'quadratic-in-out'}}]},
{'label': 'Pause',
'method': 'animate',
'args': [[None], {'frame': {'duration': 0, 'redraw': False}, 'mode': 'immediate', 'transition': {'duration': 0}}]}]}]
)
if triangles:
frames = []
fig.add_trace(go.Scatter(x=self.x_coords + [self.x_coords[0]], y=self.y_coords + [self.y_coords[0]], fill='toself', fillcolor='rgba(34, 200, 255, 0.2)',
mode='lines+markers', name='Polygon'))
triangles_x = []
triangles_y = []
for i, triangle in enumerate(triangles):
triangle_x = [triangle[0].x, triangle[1].x, triangle[2].x, triangle[0].x]
triangle_y = [triangle[0].y, triangle[1].y, triangle[2].y, triangle[0].y]
triangles_x.extend(triangle_x + [None])
triangles_y.extend(triangle_y + [None])
frame = go.Frame(data=[go.Scatter(x=triangles_x, y=triangles_y, mode='lines', line=dict(color='blue'), name='Triangles')],
name=f'frame{i}')
frames.append(frame)
fig.frames = frames
return fig
Funções para tringulação#
A função triangulate é responsável por criar e retornar uma lista com os triangulos encontrados pelo método e Ear Clipping.
def triangulate(poly):
triangles = []
vertices = poly.vertex_list[:]
while len(vertices) > 3:
for i in range(len(vertices)):
prev_index = (i - 1) % len(vertices)
next_index = (i + 1) % len(vertices)
ear_found = ear(vertices[prev_index], vertices[i], vertices[next_index],vertices)
if ear_found:
triangles.append((vertices[prev_index], vertices[i], vertices[next_index]))
#poly.plot(triangles)
vertices.pop(i)
break
triangles.append((vertices[0], vertices[1], vertices[2]))
return triangles
Análise de Complexidade#
Considerando que a cada iteração do loop externo um vértice será removido da lista de vértices, ele irá executar v-3 vezes. No pior dos casos, a orelha será encontrada sempre na última iteração do loop interno, neste loop existe o custo da chamada de ear O(v) + o custo de remover um elemento da lista (cada iteração a lista tem um elemento a menos), então o custo pode ser descrito pelo somatório abaixo:
Portanto o custo é da ordem de \(O(v^3)\) no pior caso.
Ear Clipping#
O método Ear clipping identifica triangulos no polígono ao observar se 3 vértices consecutivos formam uma orelha (o triângulo formado é convexo e nenhum outro vertice está dentro da área delimitada pelo triangulo).
def ear(prev_vertex, ear_vertex, next_vertex, vertices):
if convex(prev_vertex, ear_vertex, next_vertex):
for v in vertices:
if v != prev_vertex and v != ear_vertex and v != next_vertex:
if inTriangle(v, prev_vertex, ear_vertex, next_vertex):
return False
return True
return False
def convex(prev_vertex, curr_vertex, next_vertex):
return vetorialProduct(prev_vertex, curr_vertex, next_vertex) > 0
def vetorialProduct(v1, v2, v3):
return (v2.x - v1.x) * (v3.y - v1.y) - (v2.y - v1.y) * (v3.x - v1.x)
def inTriangle(v, v1, v2, v3):
d1 = vetorialProduct(v2,v,v1)
d2 = vetorialProduct(v3,v,v2)
d3 = vetorialProduct(v1,v,v3)
return not ((d1 < 0 or d2 < 0 or d3 < 0) and (d1 > 0 or d2 > 0 or d3 > 0))
Análise de Complexidade#
vetorialProduct
Apenas realiza operações aritméticas simples, portanto O(1)
convex
Apenas uma chamada de vetorialProduct, portanto O(1)
inTriangle
Três chamadas de vetorialProduct mais operações booleanas, portanto 3 O(1) + O(1) = O(1)
ear
Primeiro faz uma chamada de convex e no pior caso (convex sendo true) realiza um loop com o número de iterações igual ao número de vertices na entrada, dentro do loop realiza operações booleanas e chamadas de inTriangle, portanto: O(1) + O(v)O(1) = O(v)
Execução#
input = 'agp2009a-simplerand/randsimple-20-1.pol'
poly = Polygon(input)
result = triangulate(poly)
fig = poly.plot(result)
fig.show()
fig.write_html("triangulate.html")
3-Coloração#
Para encontrar o número de câmeras necessárias para cobrir toda a área a partir da triangulação, devemos encontrar uma 3-coloração da triangulação (coloração onde, em um mesmo triangulo, dois vértices não compartilhem a mesma cor).
Para esse fim, implementei uma abordagem gulosa onde, para cada triangulo da lista de triangulação, verifico as cores já utilizadas nos vertices e para cada vertice ainda não colorido, atribuo uma cor que ainda não foi utilizada.
No fim, verifico quantos vértices temos de cada cor e o número de câmeras é igual ao mínimo entre as cores.
def three_color(triangles):
color_count = {0: 0, 1: 0, 2: 0}
for triangle in triangles:
used_colors = {v.color for v in triangle if v.color is not None}
for v in triangle:
if v.color is None:
for color in range(3):
if color not in used_colors:
v.color = color
color_count[color] += 1
used_colors.add(color)
break
return color_count
Análise de Complexidade:#
Os loops internos executarão 3 vezes cada, já que temos 3 vértices por triangulo e 3 cores, sendo assim o custo é constante O(1), já o loop mais externo executa um número de vezes igual ao número de triangulos na triangulação O(t), portanto o custo é dado por:
O(1)O(t) = O(t)
def print_colors(poly,triangles):
fig = go.Figure()
fig.add_trace(go.Scatter(x=poly.x_coords + [poly.x_coords[0]], y=poly.y_coords + [poly.y_coords[0]], fill='toself', fillcolor='rgba(34, 200, 255, 0.2)',
mode='lines+markers', name='Polygon'))
frames = []
triangles_x = []
triangles_y = []
for i, triangle in enumerate(triangles):
triangle_x = [triangle[0].x, triangle[1].x, triangle[2].x, triangle[0].x]
triangle_y = [triangle[0].y, triangle[1].y, triangle[2].y, triangle[0].y]
triangles_x.extend(triangle_x + [None])
triangles_y.extend(triangle_y + [None])
fig.add_trace(go.Scatter(x=triangles_x, y=triangles_y, mode='lines', line=dict(color='blue'), name='Triangles'))
color_mapping = {0: 'blue', 1: 'green', 2: 'red'}
for v in poly.vertex_list:
color = color_mapping[v.color]
fig.add_trace(go.Scatter(x=[v.x], y=[v.y], mode='markers', marker=dict(color=color, size=10),showlegend=False))
fig.show()
fig.write_html("color.html")
Execução#
colors = three_color(result)
print_colors(poly,result)
print(f"Número de cameras: {min(colors.values())}")
Número de cameras: 6
Análise de tempo de execução por número de vértices#
def files_name(folder):
file_names = []
for file_name in os.listdir(folder):
full_path = os.path.join(folder, file_name)
if os.path.isfile(full_path):
file_names.append(file_name)
return file_names
folder = 'agp2009a-simplerand'
file_names = files_name(folder)
t = []
num_v = []
for file in file_names:
input = f"{folder}/{file}"
poly = Polygon(input)
t_i = time.time()
result = triangulate(poly)
t_f = time.time()
t.append(t_f - t_i)
num_v.append(len(poly.vertex_list))
fig = go.Figure()
fig.add_trace(go.Scatter(x=num_v, y=t, mode='markers',
marker=dict(size=10, color='blue', symbol='circle'),
name='Tempo x Número de Vértices'))
fig.update_layout(title='Relação entre Tempo e Número de Vértices',
xaxis_title='Número de Vértices',
yaxis_title='Tempo (s)',
showlegend=False)
fig.show()
fig.write_html("timexNum.html")
Referências#
https://www.geeksforgeeks.org/timing-functions-with-decorators-python/
https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf